Question: --------- Give the worst-case BigOh bounds on the running time for the given operations on the given data types. Assume that all data structures have been implemented well. get on an ArrayList get on a LinkedList push on a Stack pop on a Stack enqueue on a Queue dequeue on a Queue Question: --------- Consider a stack that is implemented using an array with space for four items. The four positions in the array have indexes 0, 1, 2, and 3. The variable top contains the index of the item on the top of the stack. (Note that for some implementations of an array stack, top contains the index of the next available space beyond the item on the top of the stack. This is not true of this implementation.) The stack is initially empty. The variable top is initialized to -1. Give the content of each position in the array and the index stored in top after each of the following stack operations are executed. push(4) push(2) pop() push(8) push(3) pop() push(1) push(7) pop() Answer: ------- 0 1 2 3 top 4 0 4 2 1 4 2 0 4 8 1 4 8 3 2 4 8 3 1 4 8 1 2 4 8 1 7 3 4 8 1 7 2 Question: --------- Consider the List class below which implements a doubly-linked list. The variable head points to the first node on the list. The variable tail points to the last node on the list. The list does not use header nodes and the list is not circular. The next pointer in the last node is null and the prev pointer in the first node is null. When the list is empty both head and tail are null. class List { class Node { Object item; Node next; Node prev; } Node head; Node tail; void insertList (List new, Node where) { } } The insertList method inserts a list into the middle of another list. The list 'new' is inserted following the node 'where'. The resulting list uses the existing nodes from the original lists. InsertList connects the node 'where' to the first node from 'new'. InsertList connects the last node from 'new' with the node following 'where'. Implement the insertList method. The following is true at the beginning of the method: a. new and where are non-null b. The two lists have no nodes in common. Your code must work correctly in general and in particular for all of the following special cases: a. new is an empty list b. where is the first node of the target list c. where is the last node of the target list Answer: ------- if (new.head == null) return; if (where == tail) { tail = new.tail; } else { new.tail.next = where.next; where.next.prev = new.tail; } new.head.prev = where; where.next = new.head; Question: --------- List the labels of the nodes of the binary tree in preorder, postorder, and inorder. A / \ B C / \ \ D E F / / \ G H I \ J / K Answer: ------- preorder A B D E G J K C F H I postorder D K J G E B H I F C A inorder D B G K J E A C H F I Question: --------- Consider the Node class below which implements a node in a binary tree. class Node { Object item; Node left; Node right; } Write a recursive method to count number of non-leaf nodes in a binary tree. Answer: ------- int countNodes(Node n) { if (n == null || n.left == null && n.right == null) return 0; else return countNodes(n.left) + countNodes(n.right) + 1; } Question: --------- Draw an expression tree for the expression. 1 + 2 * 3 / 4 - 5 + 6 / 7 * 8 / 9 Answer: ------- Precedence: */, +- Read left to right + / \ - / / \ / \ + 5 * 9 / \ / \ 1 / / 8 / \ / \ * 4 6 7 / \ 2 3 Question: --------- Give the average-case and worst-case BigOh bounds on the running time for the given operations on the given data types. Assume that all data structures have been implemented well. find on a BST find on an AVL BST find on a hash table insert on a heap delete on a heap buildHeap on an array Question: --------- Insert a node with label 3 into the binary search tree. Do not do any rebalancing of the tree. Draw the tree that results. 5 / \ 1 6 / \ \ 0 4 8 / / \ 2 7 9 Answer: ------- 5 / \ 1 6 / \ \ 0 4 8 / / \ 2 7 9 \ 3 Question: --------- Delete the node with label 1 from the binary search tree. Do not do any rebalancing of the tree. Draw the tree that results. Asnwer: ------- 5 / \ 2 6 / \ \ 0 4 8 / / \ 3 7 9 Question: --------- Insert a node with label 3 into the AVL binary search tree. Perform any needed rotations to maintain the AVL property. Draw the tree that results. 7 / \ 4 8 / \ \ 1 5 9 / \ \ 0 2 6 Answer: ------- 4 / \ 1 7 / \ / \ 0 2 5 8 \ \ \ 3 6 9 Question: --------- Delete the node with label 2 from the AVL binary search tree. Perform any needed rotations to maintain the AVL property. Draw the tree that results. 4 / \ 2 7 / / \ 1 5 8 \ \ 6 9 Answer: ------- Question: --------- The following array contains a MIN heap. Insert a node with label 0 into the MIN heap. Give the array representation of the MIN heap that results. 1 2 3 4 7 8 6 9 5 Answer: ------- 0 1 3 4 2 8 6 9 5 7 Question: --------- The following array contains a MIN heap. Execute the deleteMin operation on the MIN heap. Give the array representation of the MIN heap that results. 1 2 3 4 7 8 6 9 5 Answer: ------- 2 4 3 5 7 8 6 9 Question: --------- Execute the buildHeap (heapify) operation on the array to create a MIN heap. Give the array representation of the MIN heap that results. 9 1 8 2 7 3 6 4 5 Answer: ------- 1 2 3 4 7 8 6 9 5 Question: --------- Suppose the following array is given as input to heapsort. 9 1 8 2 7 3 6 4 5 After completing buildHeap (heapify) to make a MAX heap, the array is: 9 7 8 5 1 3 6 4 2 Give the content of the array after each major step of the remainder of heapsort. (In other words, we've already done the buildHeap part of heapsort for you. Beginning at that point, you need to give the content of the array after the completion of each major step of the algorithm. A major step is a swap followed by a percolate down.) Answer: ------- 8 7 6 5 1 3 2 4 9 7 5 6 4 1 3 2 8 9 6 5 3 4 1 2 7 8 9 5 4 3 2 1 6 7 8 9 4 2 3 1 5 6 7 8 9 3 2 1 4 5 6 7 8 9 2 1 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 Question: --------- Insert the following values into the hash table below. Use Chaining to resolve collisions. Do not grow the table or do any rehashing. Use the hash function h(x) = x % hash_table_size. 39 48 25 32 4 6 4 4 Answer: ------- 0 1 2 3 4 5 6 39 48 25 32 Question: --------- Insert the following values into the hash table below. Use Linear Probing to resolve collisions. Do not grow the table or do any rehashing. Use the hash function h(x) = x % hash_table_size. 39 48 25 32 4 6 4 4 Answer: ------- 0 1 2 3 4 5 6 32 39 25 48 Question: --------- Insert the following values into the hash table below. Use Quadratic Probing to resolve collisions. Do not grow the table or do any rehashing. Use the hash function h(x) = x % hash_table_size. 24 39 17 46 3 4 3 4 Answer: ------- 0 1 2 3 4 5 6 17 24 39 46 Question: --------- Algorithm A is O(N^3) and it completes a problem of size 1024 in 2 seconds. How long will algorithm A take to complete a problem of size 4096? How large a problem can be solved in 16 seconds using algorithm A? Answer: ------- T(N) = C.O(N) So C = T(N)/O(N) 2 / 1024^3 = x / 4096^3 ==> x = 2.4096^3/1024^3 = 128 2 / 1024^3 = 8 / x^3 ==> x = cbrt(16.1024^3/2) = 2048 Question: --------- The following table gives measured times for program A on a number of problem sizes. What big-oh function best describes the time for program A? size time 128 7 256 8 512 9 1024 10 2048 11 Answer: ------- O(log N)